#include<iostream>
#include <cstdlib>
#include <ctime>
#define max_size 10000  //正方形版图的边长
#define max_length 150
#define min_length 80   //导体的宽长范围，本例设为80~150
#define num 10000       //随机生成导体的数目

typedef struct Node    //导体结构定义
{
    int x,y,w,l;   //x,y为导体左下角坐标，w为宽，l为长
    int parent;    //将导体看作一个节点，parent为父节点
}conductor;

typedef struct Net   //线网的结构定义
{
    int number;       //线网中的导体数目
    int label[num];   //存储线网中的导体
    int root;         //线网的根节点
    struct Net *next; //指向下一个线网
}wirenet;

conductor rectg[num]; //定义全局导体数组存储形式

void generate_conductor()//随机生成num个导体
{
    for(int i = 0;i < num;i++)
    {
        rectg[i].x = rand()%(max_size-max_length);
        rectg[i].y = rand()%(max_size-max_length);//生成左下角坐标，并防止越界
        rectg[i].w = min_length + rand()%(max_length - min_length);
        rectg[i].l = min_length + rand()%(max_length - min_length);//生成宽和长
        rectg[i].parent = -1;//父节点初始设为-1
    }
}

int findPC(int i)//查找根节点并压缩路径
{
    if(rectg[i].parent == -1) return i;
    return rectg[i].parent = findPC(rectg[i].parent);
}

void Union(int i,int j)//将两个集合合并
{
    int root_i = findPC(i);
    int root_j = findPC(j);
    if(root_i != root_j) rectg[root_i].parent = root_j;
}

bool isOverlap(int i,int j)//判断两个导体是否相交
{
    if(rectg[i].x <= (rectg[j].x + rectg[j].l) && rectg[j].x <= (rectg[i].x + rectg[i].l) 
        && rectg[i].y <= (rectg[j].y + rectg[j].w) && rectg[j].y <= (rectg[i].y + rectg[i].w))
    return true;
    else return false;
}

/*设置父节点，具体方法为：对于一个导体，下标为i，找到在i之前与导体i相交的第一个导体j
把导体j的根节点设为导体i的父节点，即把导体i加入导体j所在的集合
再考虑j和i之间的导体：如果有导体k与导体i相交，那么把导体k所在集合与导体i所在集合合并
setParent()执行之后并查集建立完毕*/
void setParent()
{
    for(int i = 1;i < num;i++)
    {
        for(int j = 0;j < i;j++)
        {
            if(isOverlap(j,i))
            {
                rectg[i].parent = findPC(j);
                for(int k = j+1;k < i;k++)
                {
                    if(isOverlap(k,i))
                    {
                        Union(k,i);
                    }
                }
                break;
            }
        }
    }
}

/*设置线网，在设置父节点之后，父节点为-1的导体即为一个集合的根节点，这样的导体个数为net_num，
即线网总数*/
void setNet(int *net_num,wirenet *net_head)
{
    wirenet *tmp = net_head;
    for(int i = 0;i < num;i++)
    {
        if(rectg[i].parent == -1)
        {
            (*net_num)++;
            wirenet *newnet = (wirenet*)malloc(sizeof(wirenet));
            newnet->number = 0;
            newnet->root = newnet->label[(newnet->number)++] = i;//根节点即为导体数组的第一个导体
            tmp->next = newnet;
            tmp = newnet;
        }
    }
}

/*对除了根节点以外的节点分类，分到各个线网*/
void Classify(wirenet *head)
{
    for(int i = 0;i < num;i++)
    {
        if(rectg[i].parent == -1) continue;//跳过根节点
        wirenet *tmp = head->next;
        while(rectg[i].parent != tmp->root) tmp = tmp->next;
        tmp->label[(tmp->number)++] = i;
    }
}

int main()
{
    int net_num = 0;//初始线网个数为0
    srand(time(NULL));
    generate_conductor();//生成导体
    setParent();//生成并查集
    for(int i = 0;i < num;i++) 
    {
        int root = findPC(i);
    }
    wirenet *net_head = (wirenet*)malloc(sizeof(wirenet));//线网采用带表头的链式存储
    setNet(&net_num,net_head);
    Classify(net_head);
    wirenet *tmp = net_head->next;
    int count = 0;//线网计数
    int total = 0;//记录导体总数，检验正确性
    while(tmp)
    {
        printf("第%d个线网有%d个导体: ",count++,tmp->number);
        for(int i = 0;i < tmp->number;i++)
        {
            printf("%d ",tmp->label[i]);
        }
        printf("\n");
        total += tmp->number;
        tmp = tmp->next;
    }
    if(total == num) printf("检验导体个数正确！\n");//如果total与num相等，说明全部导体都已在线网中
    return 0;
}